package 题目集.线段树or树状数组.线段树.区间合并问题;

import java.io.*;
import java.util.Arrays;

/**
 * 序列操作
 * 给定一个长度为n的数组arr，内部只有01两种值，下标从0开始
 * 对于这个序列有五种变换操作和询问操作
 * 操作 0 l r : 把l~r范围上所有数字全改成0。
 * 操作 1 l r : 把l~r范围上所有数字全改成1
 * 操作 2 l r : 把l~r范围上所有数字全取反
 * 操作 3 l r : 询问l~r范围上有多少个1
 * 操作 4 l r : 询问l~r范围上连续1的最长子串长度
 * 测试链接 : https://www.luogu.com.cn/problem/P2572
 *
 * 思路：
 *      父范围虽然不能直接由子范围的最长长度获取。
 *      但我们可以多维护两个信息，区间最长前缀，区间最长后缀，以及区间最长长度。
 *      通过比较来获取
 * 操作 0 l r : 把l~r范围上所有数字全改成0。
 *      重置操作，如果之前已经是0，则继续懒
 * 操作 1 l r : 把l~r范围上所有数字全改成1
 *      与0相同
 * 操作 2 l r : 把l~r范围上所有数字全取反
 *      对于1的个数，让其长度-现有1的个数
 *      对于最长长度0和1互换
 * 操作 3 l r : 询问l~r范围上有多少个1
 * 操作 4 l r : 询问l~r范围上连续1的最长子串长度
 *
 */
public class ch01_综合模板 {

    static int n, m;
    static Node[] tree;
    static int[] src;
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        int tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
        tree = new Node[tn];
        src = new int[n + 1];
        for (int i = 1; i < src.length; i++) {
            src[i] = sc.nextInt();
        }
        build(1, 1, n);
        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            int l = sc.nextInt() + 1;
            int r = sc.nextInt() + 1;
            switch (op) {
                case 0:
                    update(1, l, r, 0);
                    break;
                case 1:
                    update(1, l, r, 1);
                    break;
                case 2:
                    not(1, l, r);
                    break;
                case 3:
                    int sum = sum(1, l, r);
                    pw.println(sum);
                    break;
                default:
                    int[] res = len(1, l, r);
                    pw.println(res[0]);
            }
        }
        pw.flush();
    }

    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) {
            tree[i].updateLazy(src[l]);
        } else {
            int m = l + r >> 1;
            build(i << 1, l, m);
            build(i << 1 | 1, m + 1, r);
            pull(i);
        }
    }

    public static void update(int i, int l, int r, int v) {
        if (isLazy(i, l, r)) {
            tree[i].updateLazy(v);
        } else {
            push(i);
            int m = tm(i);
            if (l <= m) {
                update(i << 1, l, r, v);
            }
            if (m < r) {
                update(i << 1 | 1, l, r, v);
            }
            pull(i);
        }
    }

    public static void not(int i, int l, int r) {
        if (isLazy(i, l, r)) {
            tree[i].notLazy();
        } else {
            push(i);
            int m = tm(i);
            if (l <= m) not(i << 1, l, r);
            if (m < r) not(i << 1 | 1, l, r);
            pull(i);
        }
    }

    //这里是真坐牢啊
    public static int[] len(int i, int l, int r) {
        if (isLazy(i, l, r)) return new int[]{tree[i].maxLen[1], tree[i].preLen[1], tree[i].postLen[1]};
        push(i);
        int m = tm(i);
        //只和左孩子有关
        if (r <= m) return len(i << 1, l, r);
        //只和有孩子有关
        if (m < l) return len(i << 1 | 1, l, r);
        int[] left = len(i << 1, l, r);
        int[] right = len(i << 1 | 1, l, r);
        int[] res = new int[3];

        int join = left[2] + right[1];
        int max = Math.max(left[0], right[0]);
        res[0] = Math.max(join, max);

        res[1] = left[0] == tree[i << 1].len ? left[1] + right[1] : left[1];
        res[2] = right[0] == tree[i << 1 | 1].len ? left[2] + right[2] : right[2];
        return res;
    }

    public static int sum(int i, int l, int r) {
        if (isLazy(i, l, r)) return tree[i].sum;
        push(i);
        int m = tm(i);
        int res = 0;
        if (l <= m) res += sum(i << 1, l, r);
        if (m < r) res += sum(i << 1 | 1, l, r);
        return res;
    }

    private static boolean isLazy(int i, int l, int r) {
        return l <= tree[i].l && tree[i].r <= r;
    }

    public static int tm(int i) {
        return tree[i].l + tree[i].r >> 1;
    }

    public static void push(int i) {
        if (tree[i].update != 2) {
            tree[i << 1].updateLazy(tree[i].update);
            tree[i << 1 | 1].updateLazy(tree[i].update);
            tree[i].update = 2;
        }
        if (tree[i].notTag) {
            tree[i << 1].notLazy();
            tree[i << 1 | 1].notLazy();
            tree[i].notTag = false;
        }
    }

    public static void pull(int i) {
        tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
        pullInfo(i, 0);
        pullInfo(i, 1);
    }

    /**
     * pos表示获取0信息，还是获取1的信息
     */
    public static void pullInfo(int i, int pos) {
        int l = i << 1, r = l | 1;
        //获取左右节点连接处的长度
        int joinLen = tree[l].postLen[pos] + tree[r].preLen[pos];
        //左右孩子的最大长度
        int len = Math.max(tree[l].maxLen[pos], tree[r].maxLen[pos]);
        tree[i].maxLen[pos] = Math.max(joinLen, len);
        tree[i].preLen[pos] = tree[l].preLen[pos] == tree[l].len ? tree[l].len + tree[r].preLen[pos] : tree[l].preLen[pos];
        tree[i].postLen[pos] = tree[r].postLen[pos] == tree[r].len ? tree[r].len + tree[l].postLen[pos] : tree[r].postLen[pos];
    }


    static class Node {
        int l, r, len;
        int sum;    //1的个数
        int[] maxLen = new int[2], preLen = new int[2], postLen = new int[2];  //分别时最长0，和最长1
        //        int[][] lens = new int[2][3];   //前面的0位置
        int update = 2;   //2表示没有揽下操作
        boolean notTag;   //是否揽下操作

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            len = r - l + 1;
        }

        public void notLazy() {
            sum = len - sum;

            int temp = maxLen[0];
            maxLen[0] = maxLen[1];
            maxLen[1] = temp;

            temp = preLen[0];
            preLen[0] = preLen[1];
            preLen[1] = temp;

            temp = postLen[0];
            postLen[0] = postLen[1];
            postLen[1] = temp;

            notTag = !notTag;
        }

        public void updateLazy(int v) {
            if (v == 1) {
                sum = len;
            } else {
                sum = 0;
            }
            maxLen[v] = len;
            preLen[v] = len;
            postLen[v] = len;

            //v^1，最低位取反
            maxLen[v ^ 1] = 0;
            preLen[v ^ 1] = 0;
            postLen[v ^ 1] = 0;

            update = v;
            notTag = false;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "l=" + l +
                    ", r=" + r +
                    ", len=" + len +
                    ", sum=" + sum +
                    ", maxLen=" + Arrays.toString(maxLen) +
                    ", preLen=" + Arrays.toString(preLen) +
                    ", postLen=" + Arrays.toString(postLen) +
                    ", update=" + update +
                    ", notTag=" + notTag +
                    '}';
        }
    }

    static class Reader {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
